{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Score Of Spliced Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumsSplicedArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #拼接数组的最大分数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个下标从 <strong>0</strong> 开始的整数数组 <code>nums1</code> 和 <code>nums2</code> ，长度都是 <code>n</code> 。</p>\n",
    "\n",
    "<p>你可以选择两个整数 <code>left</code> 和 <code>right</code> ，其中 <code>0 &lt;= left &lt;= right &lt; n</code> ，接着 <strong>交换</strong> 两个子数组 <code>nums1[left...right]</code> 和 <code>nums2[left...right]</code> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，设 <code>nums1 = [1,2,3,4,5]</code> 和 <code>nums2 = [11,12,13,14,15]</code> ，整数选择 <code>left = 1</code> 和 <code>right = 2</code>，那么 <code>nums1</code> 会变为 <code>[1,<strong><em>12</em>,<em>13</em></strong>,4,5]</code> 而 <code>nums2</code> 会变为 <code>[11,<em><strong>2,3</strong></em>,14,15]</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你可以选择执行上述操作 <strong>一次</strong> 或不执行任何操作。</p>\n",
    "\n",
    "<p>数组的 <strong>分数</strong> 取 <code>sum(nums1)</code> 和 <code>sum(nums2)</code> 中的最大值，其中 <code>sum(arr)</code> 是数组 <code>arr</code> 中所有元素之和。</p>\n",
    "\n",
    "<p>返回 <strong>可能的最大分数</strong> 。</p>\n",
    "\n",
    "<p><strong>子数组 </strong>是数组中连续的一个元素序列。<code>arr[left...right]</code> 表示子数组包含 <code>nums</code> 中下标 <code>left</code> 和 <code>right</code> 之间的元素<strong>（含</strong> 下标 <code>left</code> 和 <code>right</code> 对应元素<strong>）</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [60,60,60], nums2 = [10,90,10]\n",
    "<strong>输出：</strong>210\n",
    "<strong>解释：</strong>选择 left = 1 和 right = 1 ，得到 nums1 = [60,<em><strong>90</strong></em>,60] 和 nums2 = [10,<em><strong>60</strong></em>,10] 。\n",
    "分数为 max(sum(nums1), sum(nums2)) = max(210, 80) = 210 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]\n",
    "<strong>输出：</strong>220\n",
    "<strong>解释：</strong>选择 left = 3 和 right = 4 ，得到 nums1 = [20,40,20,<em><strong>40,20</strong></em>] 和 nums2 = [50,20,50,<em><strong>70,30</strong></em>] 。\n",
    "分数为 max(sum(nums1), sum(nums2)) = max(140, 220) = 220 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [7,11,13], nums2 = [1,1,1]\n",
    "<strong>输出：</strong>31\n",
    "<strong>解释：</strong>选择不交换任何子数组。\n",
    "分数为 max(sum(nums1), sum(nums2)) = max(31, 3) = 31 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums1.length == nums2.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums1[i], nums2[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-score-of-spliced-array](https://leetcode.cn/problems/maximum-score-of-spliced-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-score-of-spliced-array](https://leetcode.cn/problems/maximum-score-of-spliced-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[60,60,60]\\n[10,90,10]', '[20,40,20,70,30]\\n[50,20,50,40,20]', '[7,11,13]\\n[1,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        maxSum = s = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            s += y - x\n",
    "            if s < 0: s = 0\n",
    "            if s > maxSum: maxSum = s\n",
    "        return sum(nums1) + maxSum\n",
    "\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        return max(self.solve(nums1, nums2), self.solve(nums2, nums1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        maxSum = s = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            s += y - x\n",
    "            if s < 0: s = 0\n",
    "            if s > maxSum: maxSum = s\n",
    "        return sum(nums1) + maxSum\n",
    "\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        return max(self.solve(nums1, nums2), self.solve(nums2, nums1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        maxSum = s = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            s += y - x\n",
    "            if s < 0: s = 0\n",
    "            if s > maxSum: maxSum = s\n",
    "        return sum(nums1) + maxSum\n",
    "\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        return max(self.solve(nums1, nums2), self.solve(nums2, nums1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        maxSum = s = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            s += y - x\n",
    "            if s < 0: s = 0\n",
    "            if s > maxSum: maxSum = s\n",
    "        return sum(nums1) + maxSum\n",
    "\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        return max(self.solve(nums1, nums2), self.solve(nums2, nums1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        maxSum = s = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            s += y - x\n",
    "            if s < 0: s = 0\n",
    "            if s > maxSum: maxSum = s\n",
    "        return sum(nums1) + maxSum\n",
    "\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        return max(self.solve(nums1, nums2), self.solve(nums2, nums1))\n",
    "\n",
    "# class Solution:\n",
    "#     def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        \n",
    "#         def work(nums1, nums2):\n",
    "#             delta = 0\n",
    "#             tot1 = sum(nums1)\n",
    "#             ans = 0\n",
    "#             for i in range(len(nums1)):\n",
    "#                 delta += nums2[i] - nums1[i]\n",
    "#                 if delta < 0:\n",
    "#                     delta = 0\n",
    "#                 else:\n",
    "#                     ans = max(ans, tot1 + delta)\n",
    "#             return ans\n",
    "        \n",
    "#         return max(work(nums1, nums2), work(nums2, nums1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        def solve(nums1,nums2):\n",
    "            maxsum = s = 0\n",
    "            for x,y in zip(nums1,nums2):\n",
    "                s += y - x\n",
    "                if s < 0:\n",
    "                    s = 0\n",
    "                if s > maxsum:\n",
    "                    maxsum = s\n",
    "            return maxsum\n",
    "        s1 = sum(nums1)\n",
    "        s2 = sum(nums2)\n",
    "        return max(s1 + solve(nums1,nums2),s2 + solve(nums2,nums1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        maxSum = s = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            s += y - x\n",
    "            if s < 0: s = 0\n",
    "            if s > maxSum: maxSum = s\n",
    "        return sum(nums1) + maxSum\n",
    "\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        return max(self.solve(nums1, nums2), self.solve(nums2, nums1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        maxSum = s = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            s += y - x\n",
    "            if s < 0: s = 0\n",
    "            if s > maxSum: maxSum = s\n",
    "        return sum(nums1) + maxSum\n",
    "\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        return max(self.solve(nums1, nums2), self.solve(nums2, nums1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        def go(nums1, nums2):\n",
    "            maxs = 0\n",
    "            ret = 0\n",
    "            for i in range(n):\n",
    "                d = nums1[i] - nums2[i]\n",
    "                maxs += d\n",
    "                if maxs < 0:\n",
    "                    maxs = 0\n",
    "                ret = max(ret, maxs)\n",
    "            return sum(nums2) + ret\n",
    "        return max(go(nums1, nums2), go(nums2, nums1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMax(self,nums1,nums2):\n",
    "        tmp = 0 # 记录总值\n",
    "        min_pre = 0 # 记录最小前缀和\n",
    "        # 总值- 最小前缀和= 最大前缀和\n",
    "        max_pre = -float('inf') #记录最大前缀和\n",
    "        for x,y in zip(nums1,nums2):\n",
    "            tmp += y-x\n",
    "            max_pre = max(max_pre,tmp-min_pre)\n",
    "            min_pre = min(min_pre,tmp)\n",
    "        return max_pre\n",
    "\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        灵神思路：转换为最大子数组之和\n",
    "        s1 代表nums1的和\n",
    "        假设换了left - right\n",
    "        换了之后，求 s1-nums1[left:right+1]+nums2[left:right+1] 的最大值\n",
    "        求 nums2[left:right+1]-nums1[left:right+1] 的最大值\n",
    "        \"\"\"\n",
    "        ans1 = sum(nums1)+self.getMax(nums1,nums2)\n",
    "        ans2 = sum(nums2)+self.getMax(nums2,nums1)\n",
    "        return max(ans1,ans2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "s1` = s1 + diff[left] + .. + diff[right]\n",
    "s2` = s2 + diff[left] + .. + diff[right]\n",
    "'''\n",
    "class Solution:\n",
    "    def solve(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        maxSum = s = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            s += y - x\n",
    "            if s < 0: s = 0\n",
    "            if s > maxSum: maxSum = s\n",
    "        return sum(nums1) + maxSum\n",
    "\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        return max(self.solve(nums1, nums2), self.solve(nums2, nums1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        return max(self.maximums(nums1, nums2), self.maximums(nums2, nums1))\n",
    "\n",
    "    def maximums(self, nums1, nums2):\n",
    "        sum_arr = 0\n",
    "        max_sum = 0\n",
    "        res = 0\n",
    "        for i in range(len(nums1)):\n",
    "            sum_arr += nums1[i]\n",
    "            res = max(res + nums2[i] - nums1[i], 0)\n",
    "            max_sum = max(max_sum, res)\n",
    "        return sum_arr + max_sum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        maxSum = s = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            s += y - x\n",
    "            if s < 0: s = 0\n",
    "            if s > maxSum: maxSum = s\n",
    "        return sum(nums1) + maxSum\n",
    "\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        return max(self.solve(nums1, nums2), self.solve(nums2, nums1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        pmin = pmax = 0\n",
    "        tmin = 1000000000\n",
    "        tmax = -1000000000\n",
    "        n = len(nums1)\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            s = s + nums1[i] - nums2[i]\n",
    "            tmax = max(tmax, s - pmin)\n",
    "            tmin = min(tmin, s - pmax)\n",
    "            pmin = min(pmin, s)\n",
    "            pmax = max(pmax, s)\n",
    "        s1, s2 = sum(nums1), sum(nums2)\n",
    "        return max(s2 + tmax, s1 - tmin)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def solve(self, nums1:List[int], nums2:List[int])-> int:\n",
    "        maxSum = s = 0\n",
    "        for x, y in zip(nums1, nums2): \n",
    "            s += y - x # diff数组最大和\n",
    "            if s < 0: s = 0\n",
    "            if s > maxSum: maxSum = s\n",
    "        return sum(nums1) + maxSum\n",
    "\n",
    "    # 转换为最大子数组和\n",
    "    def maximumsSplicedArray(self, nums1, nums2):\n",
    "        return max(self.solve(nums1, nums2), self.solve(nums2, nums1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        def check_max_value(list1, list2):\n",
    "            sum_val = 0\n",
    "            max_val = 0\n",
    "            for item1, item2 in zip(list1, list2):\n",
    "                sum_val += item2 - item1\n",
    "                if sum_val > max_val:\n",
    "                    max_val = sum_val\n",
    "                if sum_val < 0:\n",
    "                    sum_val = 0\n",
    "            return sum(list1) + max_val\n",
    "        \n",
    "        return max(check_max_value(nums1, nums2), check_max_value(nums2, nums1))\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        s1, s2 = sum(nums1), sum(nums2)\n",
    "        \n",
    "        def dfs(nums1, nums2):\n",
    "            diff = [a - b for a, b in zip(nums1, nums2)]\n",
    "            mx = cur = 0\n",
    "            for x in diff:\n",
    "                if cur + x > x:\n",
    "                    cur += x\n",
    "                else:\n",
    "                    cur = x\n",
    "                mx = max(mx, cur)\n",
    "            return mx\n",
    "        \n",
    "        d1 = dfs(nums1, nums2)\n",
    "        d2 = dfs(nums2, nums1)\n",
    "        return max(s1, s2, s2 + d1, s1 + d2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        accu =  list(accumulate(chain([0], (n1-n2 for n1, n2 in zip(nums1, nums2)))))\n",
    "        lastMin = lastMax = 0\n",
    "        _max, _min = float('-inf'), float('inf')\n",
    "        sum2 = sum(nums2)\n",
    "        sum1 = sum2 + accu[-1]\n",
    "        for j, n in enumerate(accu, 1):\n",
    "            _max = max(_max, n - lastMin)\n",
    "            _min = min(_min, n - lastMax)\n",
    "            lastMin = min(lastMin, n)\n",
    "            lastMax = max(lastMax, n)\n",
    "        return max(sum2 + _max, sum1 - _min, sum1, sum2)\n",
    "\n",
    "        #sum2 + max(accu[j]-accu[i])\n",
    "        #sum1 - min(accu[j]-accu[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        sum1, sum2 = sum(nums1), sum(nums2)\n",
    "        accu =  list(accumulate(chain([0], (n1-n2 for n1, n2 in zip(nums1, nums2)))))\n",
    "        lastMin = lastMax = 0\n",
    "        _max, _min = float('-inf'), float('inf')\n",
    "        for j, n in enumerate(accu, 1):\n",
    "            _max = max(_max, n - lastMin)\n",
    "            _min = min(_min, n - lastMax)\n",
    "            lastMin = min(lastMin, n)\n",
    "            lastMax = max(lastMax, n)\n",
    "        return max(sum2 + _max, sum1 - _min, sum1, sum2)\n",
    "\n",
    "        #sum2 + max(accu[j]-accu[i])\n",
    "        #sum1 - min(accu[j]-accu[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        pre1 = list(accumulate(nums1, initial=0))\n",
    "        pre2 = list(accumulate(nums2, initial=0))\n",
    "        n = len(nums1)\n",
    "        ret = max(pre1[-1], pre2[-1])\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                tmp1 = pre1[-1] - pre1[j+1] + pre1[i] + pre2[j+1] - pre2[i]\n",
    "                tmp2 = pre2[-1] - pre2[j+1] + pre2[i] + pre1[j+1] - pre1[i]\n",
    "                ret = max(ret, tmp1, tmp2)\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        if sum(nums1) < sum(nums2): nums1, nums2 = nums2, nums1\n",
    "        nums = list(y - x for x, y in zip(nums1, nums2))\n",
    "        mx = mn = tmp1 = tmp2 = 0\n",
    "        for x in nums:\n",
    "            tmp1 = max(tmp1, 0) + x\n",
    "            mx = max(mx, tmp1)\n",
    "            tmp2 = min(tmp2, 0) + x\n",
    "            mn = min(mn, tmp2)\n",
    "        return max(sum(nums1) + mx, sum(nums2) - mn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n, sum1, sum2 = len(nums1), sum(nums1), sum(nums2)\n",
    "        def resolve(nums1, nums2):\n",
    "            gaps = [n1 - n2 for n1, n2 in zip(nums1, nums2)]\n",
    "            l, r, gap, mx = 0, 0, 0, 0\n",
    "\n",
    "            while l < n:\n",
    "                while r < n and gap >= 0:\n",
    "                    gap += gaps[r]\n",
    "                    r += 1\n",
    "                    mx = max(mx, gap)\n",
    "                gap -= gaps[l]\n",
    "                l += 1\n",
    "\n",
    "            return mx\n",
    "\n",
    "        return max(sum1, sum2, sum1 + resolve(nums2, nums1), sum2 + resolve(nums1, nums2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # 你可以选择执行上述操作 一次 或不执行任何操作\n",
    "        def f(nums1, nums2):\n",
    "            nums = [x2-x1 for x1, x2 in zip(nums1, nums2)]\n",
    "            for i in range(1, len(nums)):\n",
    "                if nums[i-1] >= 0:\n",
    "                    nums[i] += nums[i-1]\n",
    "            return sum(nums1) + max(0, max(nums))\n",
    "        \n",
    "        return max(f(nums1, nums2), f(nums2, nums1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #nums1>nums2 true      nums2>nums1 false\n",
    "    def getSubArray(self,l: List[int])->int:\n",
    "        N = len(l)\n",
    "\n",
    "        res = 0\n",
    "        pre = 0\n",
    "        for i in range(1,N):\n",
    "            if pre + l[i] > 0:\n",
    "                pre += l[i]\n",
    "                res = max(res,pre)\n",
    "            else:\n",
    "                pre = 0\n",
    "        return res\n",
    "\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        N = len(nums1)\n",
    "\n",
    "        l1 = [0]*(N+1)\n",
    "        l2 = [0]*(N+1)\n",
    "        # pre_sum1 = [0]*(N+1)\n",
    "        # pre_sum2 = [0]*(N+1)\n",
    "\n",
    "        sum1 ,sum2 = 0,0\n",
    "        for i in range(1,N+1):\n",
    "            # pre_sum1[i] = pre_sum1[i-1]+nums1[i-1]\n",
    "            # pre_sum2[i] = pre_sum2[i-1]+nums2[i-1]\n",
    "            sum1 += nums1[i-1]\n",
    "            sum2 += nums2[i-1]\n",
    "            l1[i] = nums2[i-1] - nums1[i-1]\n",
    "            l2[i] = nums1[i-1] - nums2[i-1]\n",
    "        \n",
    "        res1 = self.getSubArray(l1) + sum1\n",
    "        res2 = self.getSubArray(l2) + sum2\n",
    "\n",
    "        return max(res1,res2)\n",
    "\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        dpplus=[0]*n\n",
    "        dpminus=[0]*n\n",
    "        dpplus[0]=nums1[0]-nums2[0]\n",
    "        dpminus[0]=nums1[0]-nums2[0]\n",
    "        for i in range(1,n):\n",
    "            dpplus[i]=max(dpplus[i-1],0)+nums1[i]-nums2[i]\n",
    "            dpminus[i]=min(dpminus[i-1],0)+nums1[i]-nums2[i]\n",
    "        #print(dpplus,dpminus)\n",
    "        ret= max(sum(nums1)-min(dpminus),sum(nums2)+max(dpplus))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        s1 = sum(nums1)\n",
    "        s2 = sum(nums2)\n",
    "        n = len(nums1)\n",
    "        nums3, l,r,left,right = [0] * n,[0] * n,[0] * n,inf,0\n",
    "        for i in range(n):\n",
    "            nums3[i] = nums1[i] - nums2[i]\n",
    "        l[0],r[0] = nums3[0],nums3[0]\n",
    "\n",
    "        for i in range(n):\n",
    "            l[i] = min(l[i-1]+nums3[i],nums3[i])\n",
    "            r[i] = max(r[i-1]+nums3[i],nums3[i])\n",
    "            left = min(left,l[i])\n",
    "            right = max(right,r[i])\n",
    "\n",
    "        return max(s1-left,s2+right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        diff1 = list()\n",
    "        diff2 = list()\n",
    "        for i in range(len(nums1)):\n",
    "            diff1.append(nums1[i] - nums2[i])\n",
    "            diff2.append(nums2[i] - nums1[i])\n",
    "        sum1 = sum2 = 0\n",
    "        ans1 = ans2 = 0\n",
    "        for i in range(len(diff1)):\n",
    "            sum1 += diff1[i]\n",
    "            if sum1 < 0:\n",
    "                sum1 = 0\n",
    "            else:\n",
    "                ans1 = max(ans1, sum1)\n",
    "\n",
    "            sum2 += diff2[i]\n",
    "            if sum2 < 0:\n",
    "                sum2 = 0\n",
    "            else:\n",
    "                ans2 = max(ans2, sum2)\n",
    "\n",
    "\n",
    "\n",
    "        ans1 = max(ans1, sum1)\n",
    "        ans2 = max(ans2, sum2)\n",
    "        return max(sum(nums1)+ans2, sum(nums2)+ans1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s, res = 0, nums[0]\n",
    "        for num in nums:\n",
    "            s += num\n",
    "            res = max(res, s)\n",
    "            if s < 0:\n",
    "                s = 0\n",
    "        return res\n",
    "    \n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dif = [y - x for x, y in zip(nums1, nums2)]\n",
    "        return max(sum(nums1) + self.maxSubArray(dif), sum(nums2) + self.maxSubArray(list(map(lambda x: -x, dif))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        a = [nums1[i] - nums2[i] for i in range(n)]\n",
    "        b = [nums2[i] - nums1[i] for i in range(n)]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            a[i] = max(a[i], a[i] + a[i - 1])\n",
    "            b[i] = max(b[i], b[i] + b[i - 1])\n",
    "\n",
    "        return max(max(a) + sum(nums2), max(b) + sum(nums1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        def solve(nums1, nums2):\n",
    "            sm = sum(nums1)\n",
    "            nums = [nums2[i]-nums1[i] for i in range(n)]\n",
    "            pre_sm = list(accumulate(nums, initial=0))\n",
    "            mn = 0\n",
    "            mx = 0\n",
    "            for right in range(n):\n",
    "                mx = max(mx, pre_sm[right+1]-mn)\n",
    "                mn = min(mn, pre_sm[right+1])\n",
    "            sm += mx\n",
    "            return sm\n",
    "        return max(solve(nums1, nums2), solve(nums2, nums1))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        d = [nums1[i] - nums2[i] for i in range(len(nums1))]\n",
    "        d2 = [nums2[i] - nums1[i] for i in range(len(nums1))]\n",
    "\n",
    "        return max(sum(nums1) + self.maxSubArray(d2),sum(nums2) + self.maxSubArray(d))\n",
    "\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        ans = -inf\n",
    "        min_pre_sum = pre_sum = 0\n",
    "        for x in nums:\n",
    "            pre_sum += x\n",
    "            ans = max(ans, pre_sum - min_pre_sum)\n",
    "            min_pre_sum = min(min_pre_sum, pre_sum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        D = [0] * n \n",
    "        for i in range(n):\n",
    "            D[i] = nums1[i] - nums2[i]\n",
    "        dp1 = [0] * n \n",
    "        dp2 = [0] * n \n",
    "        dp1[0] = dp2[0] = D[0]\n",
    "        for i in range(1, n):\n",
    "            dp1[i] = max(D[i], dp1[i-1] + D[i])\n",
    "            dp2[i] = min(D[i], dp2[i-1] + D[i])\n",
    "        a1 = max(dp1)\n",
    "        a2 = min(dp2)\n",
    "        return max(sum(nums1) - a2, sum(nums2) + a1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        def solve(arr1, arr2):\n",
    "            diff = [y - x for x, y in zip(arr1, arr2)]\n",
    "            # print(diff)\n",
    "            n = len(arr1)\n",
    "            dp = [-inf] * n\n",
    "            dp[0] = diff[0]\n",
    "            for i in range(1, n):\n",
    "                dp[i] = max(dp[i - 1] + diff[i], diff[i])\n",
    "            return max(dp)+sum(arr1)\n",
    "        return max(solve(nums1, nums2), solve(nums2, nums1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        diff_1 = [nums1[i] - nums2[i] for i in range(len(nums1))]\n",
    "        diff_2 = [nums2[i] - nums1[i] for i in range(len(nums1))]\n",
    "        def max_subarray_sum(nums):\n",
    "            if not nums:\n",
    "                return 0\n",
    "            current_max_sum = nums[0]\n",
    "            global_max_sum = nums[0]\n",
    "            for i in range(1, len(nums)):\n",
    "                current_max_sum = max(nums[i], current_max_sum + nums[i])\n",
    "                global_max_sum = max(global_max_sum, current_max_sum)\n",
    "\n",
    "            return global_max_sum\n",
    "        k_1 = max_subarray_sum(diff_1)\n",
    "        k_2 = max_subarray_sum(diff_2)\n",
    "        ans_2 = max(sum(nums2), sum(nums2) + k_1)\n",
    "        ans_1 = max(sum(nums1), sum(nums1) + k_2)\n",
    "        print(k_1)\n",
    "        print(k_2)\n",
    "        return max(ans_1, ans_2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        def get_max_sum(diff):\n",
    "            ans = 0\n",
    "            tmp = 0\n",
    "            l = 0\n",
    "            bl,br=0,0\n",
    "            for i in range(n):\n",
    "                if tmp>0:\n",
    "                    tmp+=diff[i]\n",
    "                else:\n",
    "                    tmp=diff[i]\n",
    "                    l=i\n",
    "                if tmp>ans:\n",
    "                    bl=l\n",
    "                    br=i\n",
    "                    ans = tmp\n",
    "            return ans, bl,br\n",
    "        n=len(nums1)\n",
    "        diff1 = [nums1[i]-nums2[i] for i in range(n)]\n",
    "        diff2 = [-diff1[i] for i in range(n)]\n",
    "        # print(diff1)\n",
    "        # print(get_max_sum(diff1))\n",
    "        # print(diff2)\n",
    "        # print(get_max_sum(diff2))\n",
    "        r1 = get_max_sum(diff1)\n",
    "        r2 = get_max_sum(diff2)\n",
    "\n",
    "        # print(nums1[:r2[1]],nums1[r2[2]+1:],nums2[r2[1]:r2[2]+1])\n",
    "        # print(nums2[:r1[1]],nums2[r1[2]+1:],nums1[r1[1]:r1[2]+1])\n",
    "        return max(sum(nums1[:r2[1]])+sum(nums1[r2[2]+1:])+sum(nums2[r2[1]:r2[2]+1]),sum(nums2[:r1[1]])+sum(nums2[r1[2]+1:])+sum(nums1[r1[1]:r1[2]+1])) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        diff = [nums1[i]-nums2[i] for i in range(n)]\n",
    "        dp1,dp2 = [0]*n, [0]*n\n",
    "        dp1[0] = diff[0]\n",
    "        dp2[0] = diff[0]\n",
    "        max_diff = -float('inf')\n",
    "        min_diff = float('inf')\n",
    "        for i in range(1,n):\n",
    "            dp1[i] = diff[i] if dp1[i-1]<=0 else dp1[i-1]+diff[i]\n",
    "            dp2[i] = diff[i] if dp2[i-1]>=0 else dp2[i-1]+diff[i]\n",
    "            max_diff = max(max_diff, dp1[i])\n",
    "            min_diff = min(min_diff, dp2[i])\n",
    "        \n",
    "        sum1,sum2 = sum(nums1),sum(nums2)\n",
    "        max_res = max(sum1,sum2)\n",
    "        max_res = max(max_res, sum1 - min_diff)\n",
    "        max_res = max(max_res, sum2 + max_diff)\n",
    "        return max_res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # 需要基础知识 [最大子数组和] 经典动态规划，此题就是求出两数组差值的最大子数组和\n",
    "        n = len(nums1)\n",
    "        diff = [nums1[i]-nums2[i] for i in range(n)]\n",
    "        dp1,dp2 = [0]*n, [0]*n\n",
    "        dp1[0] = diff[0]\n",
    "        dp2[0] = diff[0]\n",
    "        max_diff = -float('inf')\n",
    "        min_diff = float('inf')\n",
    "        for i in range(1,n):\n",
    "            dp1[i] = diff[i] if dp1[i-1]<=0 else dp1[i-1]+diff[i]\n",
    "            dp2[i] = diff[i] if dp2[i-1]>=0 else dp2[i-1]+diff[i]\n",
    "            max_diff = max(max_diff, dp1[i])\n",
    "            min_diff = min(min_diff, dp2[i])\n",
    "        \n",
    "        sum1,sum2 = sum(nums1),sum(nums2)\n",
    "        max_res = max(sum1,sum2)\n",
    "        max_res = max(max_res, sum1 - min_diff)\n",
    "        max_res = max(max_res, sum2 + max_diff)\n",
    "        return max_res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        #sum'=sum-sum(nums1[right:left])+sum(nums2[right:left])=sum+diff(nums2,nums1)\n",
    "        def solve(nums1,nums2):\n",
    "            sum1=sum(nums1)\n",
    "            sum2=sum(nums2)\n",
    "            diff=[nums2[i]-nums1[i] for i in range(len(nums1))]\n",
    "            print(diff)\n",
    "            n=len(nums1)\n",
    "            dp=[0]*(n+1)\n",
    "            ans=0\n",
    "            for i  in range(1,n+1):\n",
    "                dp[i]=max(dp[i-1],0)+diff[i-1]\n",
    "                ans=max(dp[i],ans)\n",
    "            return ans+sum1\n",
    "        return max(solve(nums1,nums2),solve(nums2,nums1))\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        #sum'=sum-sum(nums1[right:left])+sum(nums2[right:left])=sum+diff(nums2,nums1)\n",
    "        def solve(nums1,nums2):\n",
    "            sum1=sum(nums1)\n",
    "            sum2=sum(nums2)\n",
    "            diff=[nums2[i]-nums1[i] for i in range(len(nums1))]\n",
    "            print(diff)\n",
    "            n=len(nums1)\n",
    "            dp=[0]*(n+1)\n",
    "            ans=0\n",
    "            for i  in range(1,n+1):\n",
    "                dp[i]=max(dp[i-1],0)+diff[i-1]\n",
    "                ans=max(dp[i],ans)\n",
    "            return ans+sum1\n",
    "        return max(solve(nums1,nums2),solve(nums2,nums1))\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # def check_max_value(list1, list2):\n",
    "        #     sum_val = 0\n",
    "        #     max_val = 0\n",
    "        #     for item1, item2 in zip(list1, list2):\n",
    "        #         sum_val += item2 - item1\n",
    "        #         if sum_val > max_val:\n",
    "        #             max_val = sum_val\n",
    "        #         if sum_val < 0:\n",
    "        #             sum_val = 0\n",
    "        #     return sum(list1) + max_val\n",
    "        \n",
    "        # return max(check_max_value(nums1, nums2), check_max_value(nums2, nums1))\n",
    "\n",
    "        def max_sub_list(input_list):\n",
    "            n = len(input_list)\n",
    "            result = [0] * n\n",
    "\n",
    "            for i in range(n):\n",
    "                if i == 0:\n",
    "                    result[i] = input_list[i]\n",
    "                else:\n",
    "                    if result[i - 1] < 0:\n",
    "                        result[i] = input_list[i]\n",
    "                    else:\n",
    "                        result[i] = input_list[i] + result[i - 1]\n",
    "            return max(result)\n",
    "        \n",
    "        sub_1 = [item1 - item2 for item1, item2 in zip(nums1, nums2)]\n",
    "        candidate1 = sum(nums2) + max_sub_list(sub_1)\n",
    "\n",
    "        sub_2 = [item2 - item1 for item1, item2 in zip(nums1, nums2)]\n",
    "        candidate2 = sum(nums1) + max_sub_list(sub_2)\n",
    "\n",
    "        return max(candidate1, candidate2)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        dpplus=[0]*n\n",
    "        dpminus=[0]*n\n",
    "        dpplus[0]=nums1[0]-nums2[0]\n",
    "        dpminus[0]=nums1[0]-nums2[0]\n",
    "        for i in range(1,n):\n",
    "            dpplus[i]=max(dpplus[i-1],0)+nums1[i]-nums2[i]\n",
    "            dpminus[i]=min(dpminus[i-1],0)+nums1[i]-nums2[i]\n",
    "        print(dpplus,dpminus)\n",
    "        ret= max(sum(nums1)-min(dpminus),sum(nums2)+max(dpplus))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        dp1 = [0]*n\n",
    "        dp2 = [0]*n\n",
    "        sum1, sum2 = 0, 0\n",
    "        for i in range(n):\n",
    "            dp1[i] = nums2[i] - nums1[i]\n",
    "            dp2[i] = nums1[i] - nums2[i]\n",
    "            sum1 += nums1[i]\n",
    "            sum2 += nums2[i]\n",
    "        \n",
    "        def MaxSubArray(nums):\n",
    "            dp = [0]*len(nums)\n",
    "            dp[0] = nums[0]\n",
    "            for i in range(1, len(nums)):\n",
    "                if dp[i-1] >= 0:\n",
    "                    dp[i] = nums[i] + dp[i-1]\n",
    "                else:\n",
    "                    dp[i] = nums[i]\n",
    "            return max(dp)\n",
    "        \n",
    "        return max(sum1 + MaxSubArray(dp1), sum2 + MaxSubArray(dp2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def max_sub(self,nums):\n",
    "        n=len(nums)\n",
    "        f=[0]*(n+1)\n",
    "        ans=max(nums)\n",
    "        if ans<=0:\n",
    "            return ans\n",
    "        for i in range(n):\n",
    "            f[i+1]=max(f[i]+nums[i],nums[i],)\n",
    "            ans=max(ans,f[i+1])\n",
    "        return ans\n",
    "\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        k1=[0]*n\n",
    "        k2=[0]*n\n",
    "        for i in range(n):\n",
    "            k1[i]=nums1[i]-nums2[i]\n",
    "            k2[i]=nums2[i]-nums1[i]\n",
    "        l1=self.max_sub(k1)\n",
    "        l2=self.max_sub(k2)\n",
    "        return max(sum(nums1)+l2,sum(nums2)+l1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        diff1=[0 for i in range(n)]\n",
    "        diff2=[0 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            diff1[i]=nums2[i]-nums1[i]\n",
    "            diff2[i]=nums1[i]-nums2[i]\n",
    "\n",
    "        def compRes(arr, diff):\n",
    "            ans=-float('inf')\n",
    "            dp=[0 for i in range(n)]\n",
    "            for i in range(n):\n",
    "                if i==0:\n",
    "                    dp[i]=diff[i]\n",
    "                    ans=diff[i]\n",
    "                dp[i]=max(diff[i], dp[i-1]+diff[i])\n",
    "                ans=max(ans, dp[i])\n",
    "            return sum(arr)+ans\n",
    "        \n",
    "        return max(compRes(nums1, diff1),compRes(nums2, diff2))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
